package common.sorting;

import org.junit.jupiter.api.Assertions;

import java.util.Arrays;

/**
 * 6. 快速排序（Quick Sort）
 * 快速排序是一种分治思想的排序算法，
 * 通过一趟排序，先选择一个基准点，将小于基准点的放在一组（例如放在基准点的左边），将大于于基准点的放在另一组（例如放在基准点的右边） （递归业务处理）
 * 最后返回基准点位置，作为下一次递归的入参（递归参数返回）
 * 左标记与右标记重合退出（递归退出条件）
 *
 * 将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
 */
public class S6_Quick {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 6, 1, 3};
        int[] expectedArr = {1, 2, 3, 5, 6, 8};
        S6_Quick.quickSort(arr, 0, arr.length - 1);
        System.out.println("arr = " + Arrays.toString(arr));
        Assertions.assertArrayEquals(expectedArr, arr);
    }

    // 接收一个数组 arr，一个低索引 low ，和一个高索引 high 作为参数
    public static void quickSort(int[] arr, int low, int high) {
        // 检查 low 是否小于 high。如果不是，则意味着数组只有一个元素或为空，因此不需要排序
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    /**
     * 取最后一个元素作为枢轴元素，将较小的元素放在左边，较大的元素放在右边
     *
     * @param arr  输入数组
     * @param low  低位索引
     * @param high 高位索引
     * @return 枢轴所在位置
     */
    private static int partition(int[] arr, int low, int high) {
        // 将最后一个元素作为枢轴元素（ arr[high] ）
        int pivot = arr[high];
        // 将 i 初始化为 low - 1，用于跟踪较小元素的索引
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                // 如果当前元素 arr[j] 小于枢轴元素，则增加 i 并交换 arr[i] 和 arr[j]
                // 较小元素索引+1
                i++;
                // 将当前元素 arr[j] 放在较小元素索引位置
                // 将较小元素放在前面
                swap(arr, i, j);
            }
            // 其他情况，则较小元素索引没有增加，说明当前元素应该放在右边
        }
        // 将枢轴元素（ arr[high] ）与索引 i + 1 处的元素交换。
        // 确保枢轴元素左边是较小元素，右边是较大元素
        swap(arr, i + 1, high);
        // 将 i + 1 作为枢轴索引返回
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
